package com.cat.DataStructure04;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/find-the-length-of-the-longest-common-prefix/
 * @create 2025/11/26 21:20
 * @since JDK17
 */

public class Solution21 {
    static int N = ((int) 1e5), cnt;
    static int[][] tree = new int[N][26];
    static void clear() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
        }
    }
    static void insert(String num) {
        int cur = 1;
        for (int i = 0, path; i < num.length(); i++) {
            path = num.charAt(i) - '0';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++ cnt;
            }
            cur = tree[cur][path];
        }
    }
    static int find(String num) {
        int cur = 1;
        for (int i = 0, path; i < num.length(); i++) {
            path = num.charAt(i) - '0';
            if (tree[cur][path] == 0) {
                return i;
            }
            cur = tree[cur][path];
        }
        return num.length();
    }
    public int longestCommonPrefix(int[] arr1, int[] arr2) {
        cnt = 1;
        int ans = 0;
        for (int x : arr1) {    //
            insert(String.valueOf(x));
        }
        for (int x : arr2) {
            ans = Math.max(ans, find(String.valueOf(x)));
        }

        clear();
        return ans;
    }
}
